package simpledb.index;

import simpledb.common.Database;
import simpledb.common.DbException;
import simpledb.common.Type;
import simpledb.common.Utility;
import simpledb.storage.*;
import simpledb.transaction.Transaction;
import simpledb.transaction.TransactionAbortedException;
import simpledb.transaction.TransactionId;
import simpledb.execution.Predicate.Op;

import java.io.*;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;

/**
 * BTreeFileEncoder 是一个工具类，用于将逗号分隔的文本文件或元组列表转换为符合 SimpleDB B+ 树结构的二进制文件。
 *
 * 它通过先将数据写入临时堆文件（HeapFile），再将其插入到 B+ 树文件中来完成编码。
 */
public class BTreeFileEncoder {

    /**
     * 将给定的元组列表转换为 B+ 树文件。
     *
     * @param tuples 要添加的元组列表
     * @param hFile 临时存储为 HeapFile 的文件
     * @param bFile 最终生成的 B+ 树文件
     * @param keyField B+ 树的键字段索引
     * @param numFields 每个元组中的字段数量
     * @return 构建好的 BTreeFile 对象
     */
    public static BTreeFile convert(List<List<Integer>> tuples, File hFile, File bFile, int keyField, int numFields)
                                                                                                                    throws IOException {
        // 创建临时文本文件
        File tempInput = File.createTempFile("tempTable", ".txt");
        tempInput.deleteOnExit();

        BufferedWriter bw = new BufferedWriter(new FileWriter(tempInput));
        for (List<Integer> tuple : tuples) {
            int writtenFields = 0;
            for (Integer field : tuple) {
                writtenFields++;
                if (writtenFields > numFields) {
                    bw.close();
                    throw new RuntimeException("Tuple has more than " + numFields + " fields: ("
                                               + Utility.listToString(tuple) + ")");
                }
                bw.write(String.valueOf(field));
                if (writtenFields < numFields) {
                    bw.write(',');
                }
            }
            bw.write('\n');
        }
        bw.close();

        // 调用另一个 convert 方法进行实际转换
        return convert(tempInput, hFile, bFile, keyField, numFields);
    }

    /**
     * 将指定的原始文本文件转换为 B+ 树文件。
     *
     * @param inFile 包含原始数据的文本文件
     * @param hFile 临时存储为 HeapFile 的文件
     * @param bFile 最终生成的 B+ 树文件
     * @param keyField 键字段索引
     * @param numFields 元组字段数
     * @return 构建好的 BTreeFile 对象
     */
    public static BTreeFile convert(File inFile, File hFile, File bFile, int keyField, int numFields)
                                                                                                     throws IOException {
        // 首先将输入文件转换为 HeapFile 格式
        HeapFileEncoder.convert(inFile, hFile, BufferPool.getPageSize(), numFields);
        HeapFile heapf = Utility.openHeapFile(numFields, hFile);

        // 创建 B+ 树文件
        BTreeFile bf = BTreeUtility.openBTreeFile(numFields, bFile, keyField);

        try {
            TransactionId tid = new TransactionId();
            DbFileIterator it = Database.getCatalog().getDatabaseFile(heapf.getId()).iterator(tid);
            it.open();
            int count = 0;
            Transaction t = new Transaction();

            while (it.hasNext()) {
                Tuple tup = it.next();
                Database.getBufferPool().insertTuple(t.getId(), bf.getId(), tup);
                count++;

                // 每插入40条记录就刷新缓冲池
                if (count >= 40) {
                    Database.getBufferPool().flushAllPages();
                    count = 0;
                }

                t.commit();
                t = new Transaction(); // 新事务
            }

            it.close();
        } catch (TransactionAbortedException | IOException | DbException te) {
            te.printStackTrace();
            return bf;
        }

        try {
            Database.getBufferPool().flushAllPages(); // 最终刷新所有页面
        } catch (Exception e) {
            e.printStackTrace();
        }

        return bf;
    }

    /**
     * 按照键字段对元组进行排序的比较器
     */
    public static class TupleComparator implements Comparator<Tuple> {
        private final int keyField;

        /**
         * 构造函数
         * @param keyField 要比较的字段索引
         */
        public TupleComparator(int keyField) {
            this.keyField = keyField;
        }

        /**
         * 比较两个元组的键字段值
         * @return -1 如果 t1 < t2；1 如果 t1 > t2；0 如果相等
         */
        public int compare(Tuple t1, Tuple t2) {
            int cmp = 0;
            if (t1.getField(keyField).compare(Op.LESS_THAN, t2.getField(keyField))) {
                cmp = -1;
            } else if (t1.getField(keyField).compare(Op.GREATER_THAN, t2.getField(keyField))) {
                cmp = 1;
            }
            return cmp;
        }
    }

    /**
     * 更高效的 B+ 树文件编码方法，支持自定义字段类型、分隔符等。
     *
     * @param tuples 要添加的元组列表
     * @param hFile 临时 HeapFile 文件
     * @param bFile 最终 B+ 树文件
     * @param npagebytes 页面大小（字节数）
     * @param numFields 每个元组字段数
     * @param typeAr 字段类型数组
     * @param fieldSeparator 字段分隔符（如 ','）
     * @param keyField 键字段索引
     * @return 构建好的 BTreeFile 对象
     */
    public static BTreeFile convert(List<List<Integer>> tuples, File hFile, File bFile, int npagebytes, int numFields,
                                    Type[] typeAr, char fieldSeparator, int keyField) throws IOException, DbException,
                                                                                     TransactionAbortedException {
        // 同样先写入临时文件
        File tempInput = File.createTempFile("tempTable", ".txt");
        tempInput.deleteOnExit();
        BufferedWriter bw = new BufferedWriter(new FileWriter(tempInput));
        for (List<Integer> tuple : tuples) {
            int writtenFields = 0;
            for (Integer field : tuple) {
                writtenFields++;
                if (writtenFields > numFields) {
                    bw.close();
                    throw new RuntimeException("Tuple has more than " + numFields + " fields: ("
                                               + Utility.listToString(tuple) + ")");
                }
                bw.write(String.valueOf(field));
                if (writtenFields < numFields) {
                    bw.write(',');
                }
            }
            bw.write('\n');
        }
        bw.close();

        // 调用最终的 convert 方法
        return convert(tempInput, hFile, bFile, npagebytes, numFields, typeAr, fieldSeparator, keyField);
    }

    /**
     * 更高效的 B+ 树编码方法，直接处理原始文件并构建完整的 B+ 树。
     *
     * @param inFile 包含原始数据的文本文件
     * @param hFile 用作中间转换的 HeapFile 文件
     * @param bFile 最终生成的 BTreeFile 文件
     * @param npagebytes 每个页面的大小（字节）
     * @param numFields 每个元组的字段数量
     * @param typeAr 元组各字段的类型数组
     * @param fieldSeparator 字段分隔符（如 ','）
     * @param keyField 主键字段索引
     * @return 构建好的 BTreeFile 对象
     * @throws IOException
     * @throws DbException
     * @throws TransactionAbortedException
     */
    public static BTreeFile convert(File inFile, File hFile, File bFile, int npagebytes, int numFields, Type[] typeAr,
                                    char fieldSeparator, int keyField) throws IOException, DbException,
                                                                      TransactionAbortedException {

        // 首先将输入文件转换为 HeapFile 格式
        HeapFileEncoder.convert(inFile, hFile, BufferPool.getPageSize(), numFields);
        HeapFile heapf = Utility.openHeapFile(numFields, hFile);

        // 从 HeapFile 中读取所有元组，并按 keyField 排序
        List<Tuple> tuples = new ArrayList<>();
        TransactionId tid = new TransactionId();
        DbFileIterator it = Database.getCatalog().getDatabaseFile(heapf.getId()).iterator(tid);
        it.open();
        while (it.hasNext()) {
            Tuple tup = it.next();
            tuples.add(tup);
        }
        it.close();
        tuples.sort(new TupleComparator(keyField));

        // 创建 BTreeFile
        BTreeFile bf = BTreeUtility.openBTreeFile(numFields, bFile, keyField);
        Type keyType = typeAr[keyField];
        int tableid = bf.getId();

        // 计算每条记录占用的字节数
        int nrecbytes = 0;
        for (int i = 0; i < numFields; i++) {
            nrecbytes += typeAr[i].getLen();
        }

        // 叶子页中的额外指针（左兄弟、右兄弟、父节点）
        int leafpointerbytes = 3 * BTreeLeafPage.INDEX_SIZE;
        int nrecords = (npagebytes * 8 - leafpointerbytes * 8) / (nrecbytes * 8 + 1); // 向下取整

        // 内部页中的额外指针（一个孩子指针 + 父指针 + 页面类型）
        int nentrybytes = keyType.getLen() + BTreeInternalPage.INDEX_SIZE;
        int internalpointerbytes = 2 * BTreeLeafPage.INDEX_SIZE + 1;
        int nentries = (npagebytes * 8 - internalpointerbytes * 8 - 1) / (nentrybytes * 8 + 1); // 向下取整

        // 添加根指针页
        bf.writePage(new BTreeRootPtrPage(BTreeRootPtrPage.getId(tableid), BTreeRootPtrPage.createEmptyPageData()));

        List<List<BTreeEntry>> entries = new ArrayList<>();

        // 准备两个页缓冲区
        List<Tuple> page1 = new ArrayList<>();
        List<Tuple> page2 = new ArrayList<>();
        BTreePageId leftSiblingId = null;

        for (Tuple tup : tuples) {
            if (page1.size() < nrecords) {
                page1.add(tup);
            } else if (page2.size() < nrecords) {
                page2.add(tup);
            } else {
                // 当前两个页都满了，写入叶子页并更新父节点
                byte[] leafPageBytes = convertToLeafPage(page1, npagebytes, numFields, typeAr, keyField);
                BTreePageId leafPid = new BTreePageId(tableid, bf.numPages() + 1, BTreePageId.LEAF);
                BTreeLeafPage leafPage = new BTreeLeafPage(leafPid, leafPageBytes, keyField);
                leafPage.setLeftSiblingId(leftSiblingId);
                bf.writePage(leafPage);
                leftSiblingId = leafPid;

                // 更新父节点，"复制上层"
                BTreeEntry copyUpEntry = new BTreeEntry(page2.get(0).getField(keyField), leafPid, null);
                updateEntries(entries, bf, copyUpEntry, 0, nentries, npagebytes, keyType, tableid, keyField);

                // 切换缓冲区
                page1 = page2;
                page2 = new ArrayList<>();
                page2.add(tup);
            }
        }

        // 处理最后一页或两页的情况
        BTreePageId lastPid = null;
        if (page2.size() == 0) {
            // 只剩一页
            byte[] lastPageBytes = convertToLeafPage(page1, npagebytes, numFields, typeAr, keyField);
            lastPid = new BTreePageId(tableid, bf.numPages() + 1, BTreePageId.LEAF);
            BTreeLeafPage lastPage = new BTreeLeafPage(lastPid, lastPageBytes, keyField);
            lastPage.setLeftSiblingId(leftSiblingId);
            bf.writePage(lastPage);
        } else {
            // 剩余两页，拆分为两个叶子页
            int remainingTuples = page1.size() + page2.size();
            List<Tuple> lastPg = new ArrayList<>();
            List<Tuple> secondToLastPg = new ArrayList<>(page1.subList(0, remainingTuples / 2));
            lastPg.addAll(page1.subList(remainingTuples / 2, page1.size()));
            lastPg.addAll(page2);
            // 写入两个叶子页并更新父节点
            byte[] secondToLastPageBytes = convertToLeafPage(secondToLastPg, npagebytes, numFields, typeAr, keyField);
            BTreePageId secondToLastPid = new BTreePageId(tableid, bf.numPages() + 1, BTreePageId.LEAF);
            BTreeLeafPage secondToLastPage = new BTreeLeafPage(secondToLastPid, secondToLastPageBytes, keyField);
            secondToLastPage.setLeftSiblingId(leftSiblingId);
            bf.writePage(secondToLastPage);

            byte[] lastPageBytes = convertToLeafPage(lastPg, npagebytes, numFields, typeAr, keyField);
            lastPid = new BTreePageId(tableid, bf.numPages() + 1, BTreePageId.LEAF);
            BTreeLeafPage lastPage = new BTreeLeafPage(lastPid, lastPageBytes, keyField);
            lastPage.setLeftSiblingId(secondToLastPid);
            bf.writePage(lastPage);

            BTreeEntry copyUpEntry = new BTreeEntry(lastPg.get(0).getField(keyField), secondToLastPid, lastPid);
            updateEntries(entries, bf, copyUpEntry, 0, nentries, npagebytes, keyType, tableid, keyField);
        }

        cleanUpEntries(entries, bf, nentries, npagebytes, keyType, tableid, keyField);

        // 设置根指针页指向最后一页
        int root = bf.numPages();
        int rootCategory = (root > 1 ? BTreePageId.INTERNAL : BTreePageId.LEAF);
        byte[] rootPtrBytes = convertToRootPtrPage(root, rootCategory, 0);
        bf.writePage(new BTreeRootPtrPage(BTreeRootPtrPage.getId(tableid), rootPtrBytes));

        setParents(bf, new BTreePageId(tableid, root, rootCategory), BTreeRootPtrPage.getId(tableid));
        setRightSiblingPtrs(bf, lastPid, null);

        Database.resetBufferPool(BufferPool.DEFAULT_PAGES);
        return bf;
    }

    /**
     * 根据左兄弟指针递归设置右兄弟指针
     *
     * @param bf BTreeFile 实例
     * @param pid 当前页 ID
     * @param rightSiblingId 当前页的右兄弟页 ID（初始为 null）
     * @throws IOException
     * @throws DbException
     */
    private static void setRightSiblingPtrs(BTreeFile bf, BTreePageId pid, BTreePageId rightSiblingId)
                                                                                                      throws IOException,
                                                                                                      DbException {

        BTreeLeafPage page = (BTreeLeafPage) bf.readPage(pid);
        page.setRightSiblingId(rightSiblingId);
        BTreePageId leftSiblingId = page.getLeftSiblingId();
        bf.writePage(page);
        if (leftSiblingId != null) {
            setRightSiblingPtrs(bf, leftSiblingId, page.getId());
        }
    }

    /**
     * 递归设置所有页面的父指针。
     *
     * @param bf BTreeFile 实例
     * @param pid 当前页面 ID
     * @param parent 父页面 ID
     * @throws IOException
     * @throws DbException
     */
    private static void setParents(BTreeFile bf, BTreePageId pid, BTreePageId parent) throws IOException, DbException {
        if (pid.pgcateg() == BTreePageId.INTERNAL) {
            // 如果是内部页，读取并设置父指针
            BTreeInternalPage page = (BTreeInternalPage) bf.readPage(pid);
            page.setParentId(parent);

            // 遍历该页的所有索引项，递归设置它们的子页的父指针
            Iterator<BTreeEntry> it = page.iterator();
            BTreeEntry e = null;
            while (it.hasNext()) {
                e = it.next();
                setParents(bf, e.getLeftChild(), pid); // 设置左孩子父指针
            }
            if (e != null) {
                setParents(bf, e.getRightChild(), pid); // 设置右孩子父指针
            }
            bf.writePage(page);
        } else { // 是叶子页
            BTreeLeafPage page = (BTreeLeafPage) bf.readPage(pid);
            page.setParentId(parent);
            bf.writePage(page);
        }
    }

    /**
     * 写出剩余的索引条目，并更新父指针。
     *
     * @param entries 剩余索引条目列表
     * @param bf BTreeFile 实例
     * @param nentries 每个内部页能容纳的最大条目数
     * @param npagebytes 页面大小（字节）
     * @param keyType 键字段类型
     * @param tableid 表 ID
     * @param keyField 主键字段索引
     * @throws IOException
     */
    private static void cleanUpEntries(List<List<BTreeEntry>> entries, BTreeFile bf, int nentries, int npagebytes,
                                       Type keyType, int tableid, int keyField) throws IOException {
        for (int i = 0; i < entries.size(); i++) {
            int childPageCategory = (i == 0 ? BTreePageId.LEAF : BTreePageId.INTERNAL);
            int size = entries.get(i).size();

            if (size <= nentries) {
                // 情况1：当前层级只有一层，直接写入内部页
                byte[] internalPageBytes = convertToInternalPage(entries.get(i), npagebytes, keyType, childPageCategory);
                BTreePageId internalPid = new BTreePageId(tableid, bf.numPages() + 1, BTreePageId.INTERNAL);
                bf.writePage(new BTreeInternalPage(internalPid, internalPageBytes, keyField));
            } else {
                // 情况2：当前层级超过一页容量，需要分裂为两个内部页
                List<BTreeEntry> secondToLastPg = new ArrayList<>(entries.get(i).subList(0, size / 2));
                List<BTreeEntry> lastPg = new ArrayList<>(entries.get(i).subList(size / 2 + 1, size));

                // 写入第一个内部页
                byte[] secondToLastPageBytes = convertToInternalPage(secondToLastPg, npagebytes, keyType,
                    childPageCategory);
                BTreePageId secondToLastPid = new BTreePageId(tableid, bf.numPages() + 1, BTreePageId.INTERNAL);
                bf.writePage(new BTreeInternalPage(secondToLastPid, secondToLastPageBytes, keyField));

                // 写入第二个内部页
                byte[] lastPageBytes = convertToInternalPage(lastPg, npagebytes, keyType, childPageCategory);
                BTreePageId lastPid = new BTreePageId(tableid, bf.numPages() + 1, BTreePageId.INTERNAL);
                bf.writePage(new BTreeInternalPage(lastPid, lastPageBytes, keyField));

                // 创建提升键并继续向上更新
                BTreeEntry pushUpEntry = new BTreeEntry(entries.get(i).get(size / 2).getKey(), secondToLastPid, lastPid);
                updateEntries(entries, bf, pushUpEntry, i + 1, nentries, npagebytes, keyType, tableid, keyField);
            }

        }
    }

    /**
     * 递归更新索引条目，并在页满时进行分裂。
     *
     * @param entries 当前索引条目列表
     * @param bf BTreeFile 实例
     * @param e 要插入的新索引条目
     * @param level 插入层级（0 表示最靠近叶子页的一层）
     * @param nentries 每页最多能容纳的条目数
     * @param npagebytes 页面大小（字节）
     * @param keyType 键字段类型
     * @param tableid 表 ID
     * @param keyField 主键字段索引
     * @throws IOException
     */
    private static void updateEntries(List<List<BTreeEntry>> entries, BTreeFile bf, BTreeEntry e, int level,
                                      int nentries, int npagebytes, Type keyType, int tableid, int keyField)
                                                                                                            throws IOException {
        // 如果当前层级不存在，创建空的条目列表
        while (entries.size() <= level) {
            entries.add(new ArrayList<>());
        }

        // 子页类型取决于当前层级是否是最底层
        int childPageCategory = (level == 0 ? BTreePageId.LEAF : BTreePageId.INTERNAL);
        int size = entries.get(level).size();

        if (size > 0) {
            // 更新最后一个条目的右子节点为新插入条目的左子节点
            BTreeEntry prev = entries.get(level).get(size - 1);
            entries.get(level).set(size - 1, new BTreeEntry(prev.getKey(), prev.getLeftChild(), e.getLeftChild()));

            // 如果当前页已满，进行分裂
            if (size == nentries * 2 + 1) {
                // 将当前层级的条目分成两部分
                ArrayList<BTreeEntry> pageEntries = new ArrayList<>(entries.get(level).subList(0, nentries));
                byte[] internalPageBytes = convertToInternalPage(pageEntries, npagebytes, keyType, childPageCategory);
                BTreePageId internalPid = new BTreePageId(tableid, bf.numPages() + 1, BTreePageId.INTERNAL);
                bf.writePage(new BTreeInternalPage(internalPid, internalPageBytes, keyField));

                // 提升中间键值作为新条目，递归插入到上一层
                BTreeEntry pushUpEntry = new BTreeEntry(entries.get(level).get(nentries).getKey(), internalPid, null);
                updateEntries(entries, bf, pushUpEntry, level + 1, nentries, npagebytes, keyType, tableid, keyField);

                // 保留剩余条目并清空当前层级
                List<BTreeEntry> remainingEntries = new ArrayList<>(entries.get(level).subList(nentries + 1, size));
                entries.get(level).clear();
                entries.get(level).addAll(remainingEntries);
            }
        }

        // 添加新条目到当前层级
        entries.get(level).add(e);
    }

    /**
     * 将一组元组转换为 BTreeLeafPage 格式的字节数组。
     *
     * @param tuples - 要写入页的元组集合
     * @param npagebytes - 页面大小（以字节为单位）
     * @param numFields - 每个元组的字段数量
     * @param typeAr - 元组字段类型的数组
     * @param keyField - B+树的键字段索引
     * @return 可传递给 BTreeLeafPage 构造函数的字节数组
     * @throws IOException
     */
    public static byte[] convertToLeafPage(List<Tuple> tuples, int npagebytes, int numFields, Type[] typeAr,
                                           int keyField) throws IOException {
        // 计算每个记录的总字节数
        int nrecbytes = 0;
        for (int i = 0; i < numFields; i++) {
            nrecbytes += typeAr[i].getLen();
        }

        // 页面中包含三个指针：父节点指针、左兄弟指针、右兄弟指针
        int pointerbytes = 3 * BTreeLeafPage.INDEX_SIZE;

        // 计算当前页面最多能容纳多少条记录（考虑位图头和记录本身的空间）
        int nrecords = (npagebytes * 8 - pointerbytes * 8) / (nrecbytes * 8 + 1); // floor 自动向下取整

        // 头部用于存储空闲槽位信息，每条记录占一位
        int nheaderbytes = (nrecords / 8);
        if (nheaderbytes * 8 < nrecords)
            nheaderbytes++; // 向上取整
        int nheaderbits = nheaderbytes * 8;

        // 初始化输出流
        ByteArrayOutputStream baos = new ByteArrayOutputStream(npagebytes);
        DataOutputStream dos = new DataOutputStream(baos);

        // 写入页面头部信息：
        // 父节点指针、左兄弟指针、右兄弟指针（初始值为 0）
        dos.writeInt(0); // parent pointer
        dos.writeInt(0); // left sibling pointer
        dos.writeInt(0); // right sibling pointer

        // 写入空闲槽位位图
        int recordcount = tuples.size();
        if (recordcount > nrecords)
            recordcount = nrecords;

        byte headerbyte = 0;
        int i = 0;
        for (i = 0; i < nheaderbits; i++) {
            if (i < recordcount)
                headerbyte |= (1 << (i % 8)); // 设置已用槽位为 1

            if (((i + 1) % 8) == 0) {
                dos.writeByte(headerbyte);
                headerbyte = 0;
            }
        }

        if (i % 8 > 0)
            dos.writeByte(headerbyte); // 写入最后未满的一个字节

        // 按照 keyField 排序后写入数据
        tuples.sort(new TupleComparator(keyField));
        for (int t = 0; t < recordcount; t++) {
            TupleDesc td = tuples.get(t).getTupleDesc();
            for (int j = 0; j < td.numFields(); j++) {
                tuples.get(t).getField(j).serialize(dos); // 序列化字段
            }
        }

        // 填充剩余空间为 0
        int paddingSize = npagebytes - (recordcount * nrecbytes + nheaderbytes + pointerbytes);
        for (int j = 0; j < paddingSize; j++)
            dos.writeByte(0);

        return baos.toByteArray(); // 返回最终的字节数组
    }

    /**
     * 用于按键排序 BTreeEntry 对象的比较器
     */
    public static class EntryComparator implements Comparator<BTreeEntry> {
        /**
         * 按键字段比较两个 BTreeEntry 的大小
         *
         * @return 如果 e1 < e2 返回 -1；如果 e1 > e2 返回 1；相等返回 0
         */
        public int compare(BTreeEntry e1, BTreeEntry e2) {
            int cmp = 0;
            if (e1.getKey().compare(Op.LESS_THAN, e2.getKey())) {
                cmp = -1;
            } else if (e1.getKey().compare(Op.GREATER_THAN, e2.getKey())) {
                cmp = 1;
            }
            return cmp;
        }
    }

    /**
     * 用于按键字段降序排列 BTreeEntry 的比较器
     */
    public static class ReverseEntryComparator implements Comparator<BTreeEntry> {
        /**
         * 按键字段比较两个 BTreeEntry 的大小（降序）
         *
         * @return 如果 e1 > e2 返回 -1；如果 e1 < e2 返回 1；相等返回 0
         */
        public int compare(BTreeEntry e1, BTreeEntry e2) {
            int cmp = 0;
            if (e1.getKey().compare(Op.GREATER_THAN, e2.getKey())) {
                cmp = -1;
            } else if (e1.getKey().compare(Op.LESS_THAN, e2.getKey())) {
                cmp = 1;
            }
            return cmp;
        }
    }

    /**
     * 将一组 BTreeEntry 转换为符合 BTreeInternalPage 格式的字节数组。
     *
     * @param entries - 要写入页面的索引条目列表
     * @param npagebytes - 页面大小（以字节为单位）
     * @param keyType - 键字段的类型（INT / STRING）
     * @param childPageCategory - 子页的类型（BTreePageId.LEAF 或 BTreePageId.INTERNAL）
     * @return 可用于构造 BTreeInternalPage 的字节数组
     * @throws IOException
     */
    public static byte[] convertToInternalPage(List<BTreeEntry> entries, int npagebytes, Type keyType,
                                               int childPageCategory) throws IOException {
        // 每个条目包含一个键和一个右子节点指针
        int nentrybytes = keyType.getLen() + BTreeInternalPage.INDEX_SIZE;

        // 额外空间：
        // 1. 一个额外的左子节点指针（每个指针占4字节）
        // 2. 父指针（4字节）
        // 3. 子页类型（1字节）
        int pointerbytes = 2 * BTreeLeafPage.INDEX_SIZE + 1;

        // 计算当前页面最多能容纳多少个条目（考虑头信息和记录本身的空间）
        int nentries = (npagebytes * 8 - pointerbytes * 8 - 1) / (nentrybytes * 8 + 1); // floor 自动向下取整

        // 头部用于存储空闲槽位信息，每个条目占一位，并且多一个 bit 表示左子节点
        int nheaderbytes = (nentries + 1) / 8;
        if (nheaderbytes * 8 < nentries + 1)
            nheaderbytes++; // 向上取整
        int nheaderbits = nheaderbytes * 8;

        // 初始化输出流
        ByteArrayOutputStream baos = new ByteArrayOutputStream(npagebytes);
        DataOutputStream dos = new DataOutputStream(baos);

        // 写入页面头部信息：
        // 父节点指针、子页类型
        dos.writeInt(0); // parent pointer
        dos.writeByte((byte) childPageCategory); // 子页类型（leaf or internal）

        // 写入空闲槽位位图
        int entrycount = entries.size();
        if (entrycount > nentries)
            entrycount = nentries;

        byte headerbyte = 0;
        int i = 0;
        for (i = 0; i < nheaderbits; i++) {
            if (i <= entrycount)
                headerbyte |= (1 << (i % 8)); // 设置已用槽位为 1（包括左子节点）

            if (((i + 1) % 8) == 0) {
                dos.writeByte(headerbyte);
                headerbyte = 0;
            }
        }

        if (i % 8 > 0)
            dos.writeByte(headerbyte); // 写入最后未满的一个字节

        // 按键排序后写入数据
        entries.sort(new EntryComparator());
        for (int e = 0; e < entrycount; e++) {
            entries.get(e).getKey().serialize(dos); // 序列化键
        }

        // 填充剩余键字段为 0
        for (int e = entrycount; e < nentries; e++) {
            for (int j = 0; j < keyType.getLen(); j++) {
                dos.writeByte(0);
            }
        }

        // 写入第一个左子节点指针
        dos.writeInt(entries.get(0).getLeftChild().getPageNumber());

        // 写入所有右子节点指针
        for (int e = 0; e < entrycount; e++) {
            dos.writeInt(entries.get(e).getRightChild().getPageNumber());
        }

        // 填充剩余右子节点指针为 0
        for (int e = entrycount; e < nentries; e++) {
            for (int j = 0; j < BTreeInternalPage.INDEX_SIZE; j++) {
                dos.writeByte(0);
            }
        }

        // 填充剩余空间为 0
        int paddingSize = npagebytes - (nentries * nentrybytes + nheaderbytes + pointerbytes);
        for (int j = 0; j < paddingSize; j++)
            dos.writeByte(0);

        return baos.toByteArray(); // 返回最终的字节数组
    }

    /**
     * 构造一个符合 BTreeRootPtrPage 格式的字节数组。
     *
     * @param root - 根页面的页号
     * @param rootCategory - 根页面的类型（leaf 或 internal）
     * @param header - 第一个 Header Page 的页号
     * @return 可用于构造 BTreeRootPtrPage 的字节数组
     * @throws IOException
     */
    public static byte[] convertToRootPtrPage(int root, int rootCategory, int header) throws IOException {

        // 创建输出流
        ByteArrayOutputStream baos = new ByteArrayOutputStream(BTreeRootPtrPage.getPageSize());
        DataOutputStream dos = new DataOutputStream(baos);

        // 写入根页面指针
        dos.writeInt(root); // root pointer
        // 写入根页面类型（leaf or internal）
        dos.writeByte((byte) rootCategory);
        // 写入 Header Page 指针
        dos.writeInt(header); // header pointer

        return baos.toByteArray();
    }
}
